#include<bits/stdc++.h>
using namespace std;
struct node
{
    int l,li,r,ri;
};
vector<node> b,ans;
int a[200005],n,ans2;

bool cmp(node x,node y)
{
    return (x.ri-x.li)<(y.ri-y.li);
}
bool is_bh(node x,node y)
{
    return x.li>y.li&&x.ri<y.ri;
}
bool check(node x)
{
    
    int bh_sum=0;
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i].l!=-1&&is_bh(ans[i],x))
        {
            bh_sum+=ans[i].r;
        }
    }
    if(x.r>bh_sum)return 1;//if = ?
    return 0;
}
void dele_bh(node x)
{
    for(int i=0;i<ans.size();i++)
    {
        if(is_bh(ans[i],x))
        {
            ans[i].l=-1;;
        }
    }
}
void work()
{
    b.clear();ans.clear();
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(a[i]==a[j])
            {
                b.push_back(node{a[i],i,a[j],j});//if break?
            }
        }
    }
    sort(b.begin(),b.end(),cmp);
    //for(int i=0;i<b.size();i++)
        //cout<<b[i].l<<' '<<b[i].li<<' '<<b[i].r<<' '<<b[i].ri<<'\n';
    for(int i=0;i<b.size();i++)
    {
        if(check(b[i]))
        {
            ans.push_back(b[i]);
            dele_bh(b[i]);
        }
    }
    int ANS=0;
    for(int i=0;i<ans.size();i++)
    {
        if(ans[i].l!=-1)ANS+=ans[i].r;
    }
    cout<<ANS<<'\n';
}


void dfs(int dep,int la1,int la2,int sum)
{
    if(dep>n)
    {
        ans2=max(ans2,sum);
        return;
    }
    int new_sum=sum;
    if(a[dep]==la1)new_sum+=a[dep];
    dfs(dep+1,a[dep],la2,new_sum);

    new_sum=sum;
    if(a[dep]==la2)new_sum+=a[dep];
    dfs(dep+1,la1,a[dep],new_sum);
}
void work2()
{
    ans2=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1,0,0,0);
    cout<<ans2<<'\n';
}

int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        if(n<25)
            work2();
        else work();
    }
    return 0;
}